1. Field of the Invention
This invention relates to a method for detecting collisions in a transmission channel which is accessed by stations using a distributed queueing random access protocol (DQRAP) wherein broadcast channel time is divided into a plurality of slots, each of which includes one data slot and one or more control minislots, and each sending station maintains two common distributed queues. One queue, the data transmission queue, is used to organize the order of data transmission, and the other queue, the collision resolution queue, is used to resolve collisions that have occurred and to prevent collisions by new arrivals. The protocol includes data transmission rules, request transmission rules and queueing discipline rules. In an alternative embodiment a station employing the two distributed queues also can send a control minislot containing a destination identifier and a data slot length indicator.
2. Description of Prior Art
Investigation of multiple, random access control methods has been an active research area since as early as 1970. The well known CSMA protocols were then developed and later followed by multiple access methods which utilized various forms of feedback to improve performance by reducing or avoiding the occurrence of collisions. These included collision resolution schemes, now called tree-and-window collision resolution algorithms (CRA). The CSMA protocols achieved high throughput with minimal delay with low offered loads, and they have gained wide application in local area networks. In fact with zero propagation delay, collisions in slotted CSMA can be completely avoided and the performance of CSMA then corresponds to that of a perfect scheduling protocol, such as an M/D/1 queue. However, the CSMA protocols are not stable when traffic is heavy and while dynamic control mechanisms can improve performance, the unstable nature cannot be changed.
The first CRA included a tree algorithm which achieved maximum throughput of 0.43, and was stable for all input rates of less than 0.43. This stable characteristic of the tree algorithm has attracted much attention in both the communications and information theory areas. The tree algorithm was improved by increasing the maximum throughput to 0.462. The next improvement was the 0.487 window protocol. The tree and window protocols are based on efficient use of channel feedback to resolve collisions and require transmitter coordination. It has been shown that the upper bound of throughput of all algorithms based on ternary feedback is 0.568, the tightest upper bound to date.
It is widely believed that the best achievable throughput is in the neighborhood of 0.5. If the amount of channel feedback is increased to indicate the number of packets involved in each collision, then throughput up to one may be achieved. However, the known algorithms in this context achieve only 0.533 throughput. Some known protocols achieve higher throughput than 0.5 by using control minislots (CMS) to obtain extra feedback. Among such known protocols, the announced arrival random access protocols (AARA) achieve the best performance with respect to throughput and delay characteristics. With three minislots the AARA protocol achieves a throughput of 0.853. However, to achieve throughput approaching one, the AARA protocol must use an infinite number of minislots. Obviously, the AARA protocols do not achieve or approach the bound of performance in this context. All existing tree protocols seem to use data slots to resolve collisions. In this process, channel capacity is lost either to empty slots or to collisions. All suggested improvements to tree protocols increased the channel throughput by reducing empty slots and collided slots, but none eliminated this type of loss.
It has been known for some time that digital data can be transmitted over serial and broadcast media. A problem continuously faced by the designer of digital data communication equipment is efficient utilization of the transmission and receiving equipment as well as efficient utilization of the medium or channel over which the data is to be transmitted and received. A number of approaches have been developed in the past, most of which suffer from one or more drawbacks. One of the earlier well-known digital data control systems is the Aloha System, originally developed for a packet radio application at the University of Hawaii and put into public use more than twenty years ago. The Aloha System, in its pure form, is based upon a broadcast transmission followed by a listening period for an acknowledge signal from the receiving station. If no acknowledge signal is received, the transmitting station then retransmits randomly until it receives an acknowledgement signal indicating that successful transmission has been achieved. The Aloha System, in its pure form, allows variable length data slots or frames to be transmitted. However, Aloha suffers from the drawback that, on average, its Aloha maximum efficiency is about 18%.
An improvement over the pure Aloha system is slotted Aloha, which fixes the periods for data transmission to a fixed time or a slot time, also known as a data slot. The system uses the same transmission followed by acknowledgement as the pure Aloha but, due to the use of the fixed length data slots, achieves, maximally, up to 36% efficiency in channel utilization. CSMA systems have been developed which are useful for relatively short length systems, where xe2x80x9caxe2x80x9d, which is the ratio of the signal propagation delay to the time duration between the beginning of frame or slot transmission and the termination of frame or slot transmission, is less than 0.5. In those systems, CSMA is attractive. In order to practice the CSMA protocol, each station sharing a broadcast or other medium xe2x80x9clistensxe2x80x9d to the medium and does not initiate a transmission unless its response to listening indicates that the channel is currently unoccupied by a transmission from any other station. Such systems, however, do not achieve high throughput, in part because the maximal dimension of the system is dictated by the propagation delay to frame length ratio. This does not provide for efficient channel utilization.
The CSMA/CD system provides an improved and more efficient protocol over that of the CSMA system because the CSMA system, upon hearing a collision occurring, backs off for a period of time determined by an exponential back-off algorithm which is executed in appropriate software or hardware logic.
A significant improvement over the prior systems involves a digital protocol wherein a number of nodes, or stations, may all be connected to a single broadcast medium, whether wired or wireless, or may be connected in a star configuration or other configurations. Each of the stations includes a nodal apparatus which has a storage which may include a memory for storing a conflict resolution queue and a transmission queue. The system is a slotted system in that periodically, and at regular intervals, one or more control minislot signals may be transmitted from a particular station followed by a data transmission in a data slot in response to conditions in the conflict resolution queue and in the transmission queue. Such a system achieves significantly improved utilization of the channel capacity, in some cases, approaching 1.00 of the channel capacity.
One of the drawbacks of such a distributed queue random access protocol system, which is disclosed in Xu, Wenxin, xe2x80x9cDistributed Queuing Random Access Protocols for a Broadcast Channel,xe2x80x9d Illinois Institute of Technology, Chicago, Ill., December, 1990, and U.S. Pat. No. 5,390,181, lies in the fact that for certain systems, such as local area network systems which not only have bursty transmission, but have transmission wherein the amount of data to be transmitted may vary significantly from time to time. Thus, if the fixed length data slot used in the basic distributed queue random access protocol is employed, there may be some channel inefficiencies which result due to the data slot not being entirely filled by a particular data transmission, thus causing some wastage of channel capacity. Likewise, inefficiency may result because a frame longer than the data slot must be segmented and, of course, associated with its own respective control minislots which effectively add unneeded overhead. What is needed is a system which employs conflict resolution queues and transmission queues in combination with a flexible data slot assignment and control system to enhance further the inherent efficiencies in the distributed queue random access protocol system.
It is one object of this invention to provide a method for controlling multiple access of a transmission channel through the detection of collisions by comparing a plurality of different patterns within a control minislot.
It is another object of this invention to assign different Binomial coefficients to a plurality of sending stations and to use such Binomial coefficients to detect collisions.
It is still another object of this invention to use a distributed queueing random access protocol in various system, such as with packet radio, satellite, broadband cable, cellular voice, and other passive optical networks.
The distributed queueing random access protocol (DQRAP) of this invention is a stable random multiple access protocol for use in a broadcast channel shared by an infinite number of bursty stations. The DQRAP according to this invention is based on tree protocols with minislots. These tree protocols use minislots to provide extra feedback in order to reduce the number of empty and collided slots. However, the DQRAP according to this invention uses the minislots for collision resolution and resolves the data slots for data transmission. Implicitly, even though counters are often used, conventional tree algorithms use a single queue which performs as a collision resolution queue. The method according to this invention achieves the desired performance by introducing an additional queue, the data transmission queue, to schedule data transmission parallel to contention resolution and thereby nearly eliminating contention in the data slots. The DQRAP of this invention, using as few as three minislots, achieves a performance level which approaches that of hypothetical perfect scheduling protocol, such as the M/D/1 system, with respect to throughput and delay.
The present invention also relates to nodal apparatus and networks employing multiple distributed queues wherein the efficiency of channel utilization, whether on a broadcast channel, star channel or other types of channels is substantially equivalent to the offered load up to an offered load of one. In the event that the offered load is greater than the channel capacity, the inventive system allows the channel utilization to remain at one independently of offered loads of one or above, less the overhead allocated to the control minislots.
The system which provides sufficient channel utilization is a distributed queue random access protocol (DQRAP) system, wherein multiple nodes each include a memory for storing a conflict resolution queue which includes a counter that is incremented when a collision occurs during any control minislot (CMS). An index or other identification is attached to a particular count when the local station has attempted to transmit during a control minislot and detects a collision signal resulting from that control minislot. A second queue is also kept within the nodal station, which queue contains a counter that is incremented for each collision-free minislot access. An index is attached to particular queue numbers to identify the ordinal numeral, or position in the queue, occupied by the particular local station. Thus, each station maintains a conflict resolution queue with a counter having been marked to identify when the station may seek access to control minislots and a transmission queue indicating when the station may transmit during data slots. It may be appreciated that when there is no minislot collision and the transmission queue counter is zero at a local station, the station may immediately transmit its data during that data slot. Each station is further provided with a system for sending multiple data slots following the control minislot request containing a destination identifier and the length or number of data slots requested to accommodate, to some extent, variable length data sets which are to be transmitted over a long haul system.
Other advantages of the present invention will become apparent to one of ordinary skill in the art, upon a perusal of the following specification and claims in light of the accompanying drawings.